package com.muchfish.algorithm.stack;

import java.util.ArrayDeque;
import java.util.Deque;

public class RainWater {
    public int trap(int[] height) {
        //特殊判断
        if (height == null) {
            return 0;
        }
        //构造单调栈,此处两边不需要哨兵,原因是因为两侧肯定是装不了水的,如果加入了哨兵要么就让两侧能装水了,要么就是导致中间的计算结果不正确
        Deque<Integer> stack = new ArrayDeque();
        //定义最大值
        int max = 0;
        //数组元素依次入栈
        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[i] >= height[stack.peek()]) {
                int p = stack.pop();
                if (!stack.isEmpty()) {
                    max += (Math.min(height[stack.peek()], height[i]) - height[p]) * (i - stack.peek() - 1);
                }
            }
            stack.push(i);
        }
        return max;
    }
}
